import BaseSort from './BaseSort'

export default class QuickSort extends BaseSort{
    constructor(){
        super();

    }

    //pivotIndex  "基准"（pivot）

    // 实现sort方法
    sort(){
        let arr = this.getData();
        let res = this._quickSortByPivot(arr);
        this.setResult(res);
    }


    /* 
    *"快速排序"的思想很简单，整个排序过程只需要三步：
    *（1）在数据集之中，选择一个元素作为"基准"（pivot）。
    *（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
    *（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
    */
    _quickSortByPivot(arr){
        if(arr.length <= 1) return arr;
        // 两个标记：i,j
        let pivot = this.getPivot(arr);//基准值
        let left = [];  //左边集合
        let right = []; //右边集合
        // console.log('pivot',pivot);
        this.updateLoopTimes();//记录循环
        // 内容分左右
        for(let i=0; i<arr.length; i++){
            this.updateCompareTimes();
            if(arr[i] < pivot){//如果当前值小于基准值，放到左边数组
                left.push(arr[i])
            }else{
                right.push(arr[i]);
            }
        }
        return this._quickSortByPivot(left).concat(pivot, this._quickSortByPivot(right));
    }

    //获取基准值
    getPivot(arr){
        let pivotIndex = Math.floor(arr.length / 2);
        return arr.splice(pivotIndex,1)[0];
    }
}